package com.algorithms.techniques.graph;

import java.util.HashMap;
import java.util.Map;

import com.algorithms.absdatatypes.IDisjointSet;

public class DisjointSet<T> implements IDisjointSet<T>
{
 
   Map<T,T> parentMap =null;
   Map<T,Integer> rankMap =null;
   public DisjointSet()
   {
	   
	   parentMap=new HashMap<T,T>();
	   rankMap=new HashMap<T,Integer>();
   }
   
	
	public T findSet(T x) {
		
		T parent =parentMap.get(x);
		if(!parentMap.get(x).equals(x) )
		{
			parentMap.put(x,findSet(parent));
		}
		return parent; 	
	}

	
	public void makeSet(T x) {
		
		parentMap.put(x, x);
		rankMap.put(x, 0);
	}

	
	public T union(T x, T y) 
	{
		return link(findSet(x) ,findSet(y));
		
	}

    private T  link(T x ,T y)
    {
    	T returnRoot=null;
		if(rankMap.get(x) > rankMap.get(y))
		{
			parentMap.put(y, x);
			returnRoot=x;
		}
		else if(rankMap.get(x) < rankMap.get(y))
		{
			parentMap.put(x, y);
			returnRoot=y;
		}
		else
		{
			rankMap.put(x, rankMap.get(x) +1);
			parentMap.put(y, x);
			returnRoot=x;
		}
    	return returnRoot;
    	
    }
   
}
